package thired.class10_graph;

import java.util.ArrayList;
import java.util.HashMap;

public class Class06_TopologicalOrderDFS1 {
    // 不要提交这个类
    public static class DirectedGraphNode {
        public int label;
        public ArrayList<DirectedGraphNode> neighbors;

        public DirectedGraphNode(int x) {
            label = x;
            neighbors = new ArrayList<DirectedGraphNode>();
        }
    }
    public class Record{
        public DirectedGraphNode node;
        public long height;

        public Record(DirectedGraphNode node, long height) {
            this.node = node;
            this.height = height;
        }
    }

    public  ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph){
        HashMap<DirectedGraphNode, Record> order = new HashMap<>();
        for (DirectedGraphNode cur : graph) {
            f(cur, order);
        }
        ArrayList<Record> recordArr = new ArrayList<>(order.values());
        recordArr.sort(((o1, o2) -> {return (int) (o2.height- o1.height);}));
        ArrayList<DirectedGraphNode> res = new ArrayList<>();
        for (Record record : recordArr) {
            res.add(record.node);
        }
        return res;

    }


    public Record f(DirectedGraphNode node, HashMap<DirectedGraphNode, Record> order){
        if(order.containsKey(node)){
            return order.get(node);
        }
        long follow = 0;
        for (DirectedGraphNode neighbor : node.neighbors) {
            follow = Math.max(follow, f(neighbor, order).height);
        }
        Record res = new Record(node,++follow);
        order.put(node,res);
        return res;
    }
}
